On the equivalence between low rank matrix completion and tensor rank

摘要

The Rank Minimization Problem asks to find a matrix of lowest rank inside alinear variety of the space of n x n matrices. The Low Rank Matrix Completionproblem asks to complete a partially filled matrix such that the resultingmatrix has smallest possible rank. The Tensor Rank Problem asks to determine the rank of a tensor. We show thatthese three problems are equivalent: each one of the problems can be reduced tothe other two.